package com.tgy.algorithm._经典题目01;

import java.util.*;

/**
 * 给定一个由字符串组成的数组String日strs，给定一个正数K返回词频最大的前K个字符串，假设结果是唯一的
 */
public class _019_词频最大的前K个字符串 {

    public static List<String> getMaxKTimes(String[] strs, int k) {

        if (strs == null || strs.length == 0) {
            return null;
        }

        HashMap<String, Integer> hashMap = new HashMap<>();

        for (String str : strs) {
            int key = 1;
            if (hashMap.containsKey(str)) {
                key = hashMap.get(str) + 1;
            }
            hashMap.put(str,key);
        }

        PriorityQueue<String> minHeap = new PriorityQueue<>((one, two) -> {
            return hashMap.get(one) - hashMap.get(two);
        });

        for (String string : hashMap.keySet()) {
            if (minHeap.size() < k) {
                minHeap.add(string);
            }else {
                String topStr = minHeap.peek();
                if (hashMap.get(topStr) < hashMap.get(string)) {
                    minHeap.poll();
                    minHeap.add(string);
                }
            }
        }

        ArrayList<String> rets = new ArrayList<>();

        while (!minHeap.isEmpty()) {
            rets.add(minHeap.poll());
        }

        return rets;
    }

    static class KeyTimeNode {
        public String key;
        public int time;
        KeyTimeNode(String key,int time) {
            this.key = key;
            this.time = time;
        }
    }

    public static List<String> getMaxKTimesBySort(String[] strs, int k) {

        if (strs == null || strs.length == 0) {
            return null;
        }

        HashMap<String, Integer> hashMap = new HashMap<>();

        for (String str : strs) {
            int key = 1;
            if (hashMap.containsKey(str)) {
                key = hashMap.get(str) + 1;
            }
            hashMap.put(str,key);
        }

        int len = hashMap.size();

        KeyTimeNode[] keyTimeNodes = new KeyTimeNode[len];
        int index = 0;
        for (String string : hashMap.keySet()) {
            keyTimeNodes[index++] = new KeyTimeNode(string,hashMap.get(string));
        }

//        System.out.println("1111");

        KeyTimeNode k1 = findK(keyTimeNodes, k);
        ArrayList<String> list = new ArrayList<>();
        for (KeyTimeNode keyTimeNode : keyTimeNodes) {
            if (keyTimeNode.time >= k1.time) {
                list.add(keyTimeNode.key);
            }
        }

        return list;
    }

    public static KeyTimeNode findK(KeyTimeNode[] nodes,int k) {

        int left = 0;
        int right = nodes.length - 1;
        while (true) {
            int[] ints = doFindK(nodes, left, right);
            if (ints[0] <= k && k <= ints[ints.length - 1]) {
                return nodes[k];
            }else if (k < ints[0]) {
                right = ints[0];
            }else if( k > ints[ints.length - 1] ) {
                left = ints[ints.length - 1];
            }
        }

//        return null;
    }

    public static int[] doFindK(KeyTimeNode[] nodes,int start,int end) {

        int leftIndex = start - 1;
        int rightIndex = end - 1;
        int index = start;
        int time = nodes[index].time;

        while (index <= rightIndex) {
            KeyTimeNode node = nodes[index];
            if (node.time < time) {
                if (leftIndex + 1 != index) {
                    swap(nodes,leftIndex+1,index);
                }
                leftIndex++;
                index++;
            }else if (node.time > time) {
                swap(nodes,rightIndex,index);
                rightIndex--;
            }else {
                index++;
            }
        }

        swap(nodes,rightIndex+1,end);
        int[] ints = new int[2];
        ints[0] = leftIndex+1;
        ints[1] = rightIndex+1;
        return ints;
    }

    public static void swap(KeyTimeNode[] nodes,int x, int y) {
        KeyTimeNode tmp = nodes[x];
        nodes[x] = nodes[y];
        nodes[y] = tmp;
    }


    public static void main(String[] args) {
        String[] rets = {"abc","dba","abc","dba","ccc","dba","ghj","lop"};
//        List<String> maxKTimes = getMaxKTimes(rets, 2);
//        System.out.println(maxKTimes);
        getMaxKTimesBySort(rets,2);
    }
}
